Search results for "Set packing"

showing 3 items of 3 documents

Improved polyhedral descriptions and exact procedures for a broad class of uncapacitated p-hub median problems

2019

Abstract This work focuses on a broad class of uncapacitated p-hub median problems that includes non-stop services and setup costs for the network structures. In order to capture both the single and the multiple allocation patterns as well as any intermediate case of interest, we consider the so-called r-allocation pattern with r denoting the maximum number of hubs a terminal can be allocated to. We start by revisiting an optimization model recently proposed for the problem. For that model, we introduce several families of valid inequalities as well as optimality cuts. Moreover, we consider a relaxation of the model that contains several sets of set packing constraints. This motivates a pol…

050210 logistics & transportationMathematical optimizationClass (set theory)Computer science05 social sciencesTransportation010501 environmental sciencesManagement Science and Operations Research01 natural sciencesData setIdentification (information)Terminal (electronics)Set packing0502 economics and businessOrder (group theory)Relaxation (approximation)Branch and cut0105 earth and related environmental sciencesCivil and Structural EngineeringTransportation Research Part B: Methodological
researchProduct

Dichotomies properties on computational complexity of S-packing coloring problems

2015

This work establishes the complexity class of several instances of the S -packing coloring problem: for a graph G , a positive integer k and a nondecreasing list of integers S = ( s 1 , ? , s k ) , G is S -colorable if its vertices can be partitioned into sets S i , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.

Discrete mathematicsDichotomyComputational complexity theory010102 general mathematics0102 computer and information sciences01 natural sciencesGraphTheoretical Computer ScienceCombinatoricsIntegerSet packing010201 computation theory & mathematicsComplexity classDiscrete Mathematics and CombinatoricsPairwise comparison0101 mathematicsColoring problemMathematicsDiscrete Mathematics
researchProduct

Matheuristics for the irregular bin packing problem with free rotations

2017

[EN] We present a number of variants of a constructive algorithm able to solve a wide variety of variants of the Two-Dimensional Irregular Bin Packing Problem (2DIBPP). The aim of the 2DIBPP is to pack a set of irregular pieces, which may have concavities, into stock sheets (bins) with fixed dimensions in such a way that the utilization is maximized. This problem is inspired by a real application from a ceramic company in Spain. In addition, this problem arises in other industries such as the garment industry or ship building. The constructive procedure presented in this paper allows both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientation…

Mathematical optimization021103 operations researchInformation Systems and ManagementGeneral Computer ScienceBin packing problemESTADISTICA E INVESTIGACION OPERATIVA0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchStrip packingTwo-dimensional irregular bin packingConstructiveIndustrial and Manufacturing EngineeringBinCutting and packingSet packingCutting stock problemModeling and Simulation0202 electrical engineering electronic engineering information engineeringInteger Programing020201 artificial intelligence & image processingFree rotationFinite setMathematics
researchProduct